# -*- coding: utf-8 -*-

class Solution(object):
        def missingNumber(self, nums):
            """
        :type nums: List[int]
        :rtype: int
        """
        return(int(len(nums)*(len(nums)+1)/2)-sum(nums))



sss =  Solution()
qqq = sss.missingNumber([2218,3507,8616,5598,6827,9959,186,6945,2998,556,827,2465,7063,1194,8680,8825,6464,5198,1920,8167,5960,4608,2132,4969,5046,6920,4025,9794,8495,6632,8082,5979,736,5743,4785,7729,2652,1870,7526,3714,2805,1712,1903,5523,9815,9069,5279,3935,8454,8920,9051,2650,9796,7887,7667,6403,5367,1462,855,3545,3355,6474,8506,8676,2994,5488,2301,6251,4269,4205,7540,3654,4804,1319,7847,2291,583,243,7842,2881,4674,3908,8419,5593,114,6495,5736,7631,580,8201,4676,51,6156,3036,406,4305,8,1235,1114,9632,3479,6472,5640,7913,8487,5343,9672,3193,6045,2036,240,1261,5449,1881,5509,9904,5707,1913,1918,6815,7854,9761,2795,5811,1825,4453,6713,4678,4628,868,997,7490,9662,8598,6626,4661,3047,6267,4876,5966,1357,9081,9322,2679,775,2513,9584,6613,5717,6857,3203,8924,3234,7249,1058,8017,7103,2710,7143,2453,3143,3520,4312,9521,7192,8162,4688,3152,8349,4929,3271,8026,9465,6151,3933,4388,9946,455,2006,2612,8444,4700,4046,9391,9055,7274,1248,215,4998,6813,104,5514,1518,3114,6990,8894,3207,1135,8224,8318,4015,8555,439,1012,5678,6209,8402,6786,8431,6527,2491,5301,1359,5127,6819,4019,6483,6153,5735,893,9877,4863,1567,7402,7619,4963,5424,8239,3683,7530,9645,2828,8993,2551,3629,27,3799,6404,1863,8571,342,9066,5585,3352,1092,425,4541,1106,611,3407,3924,371,909,2681,2308,2302,4342,2056,4789,1393,7572,8077,7059,2016,372,507,498,8691,3763,1243,5970,3438,2086,2469,9062,2381,4292,4590,4195,7283,1144,3012,8490,2362,6614,5417,428,4485,7982,2471,3057,3802,9999,6768,8484,684,857,3063,4941,2761,6633,9491,8258,966,6707,8340,3575,3511,2875,9311,9253,1387,7938,3025,8726,4048,1172,8012,5436,6282,3504,1212,2111,4707,3492,829,4499,9682,3293,185,2436,8992,4275,3955,8473,4850,9427,4510,3096,2031,9956,4983,6926,7949,2777,7625,216,5481,1059,9538,3495,4977,1773,3220,9846,5701,8568,9834,8606,4653,4984,4719,2976,4494,5067,284,8066,6322,999,2452,572,9200,6712,7584,8125,4752,7545,9480,4414,8189,7880,6034,1296,3564,3991,4754,374,5280,7185,1782,4156,988,8413,2518,6311,7839,643,7493,2523,4271,2716,9698,5611,6215,7633,3876,2189,4925,847,5443,4368,7098,5522,367,4992,6200,3288,8254,8295,152,6730,7173,6879,9927,623,8904,5078,2606,3280,836,3805,9757,8563,6337,7570,6133,5605,7065,5661,9995,2300,3372,405,2502,9650,6126,6252,6686,3797,3669,4238,6552,9637,165,5052,8710,3751,5001,713,7016,7314,5755,5043,8461,6905,9566,2253,4740,1179,4605,7846,2131,995,1245,5974,1851,9461,2275,6447,5400,9085,1064,882,5551,4881,717,7061,8342,908,8259,6961,5875,4859,8214,3338,7004,6042,4199,5240,5645,9651,1009,6591,1423,1672,8537,3346,9140,4725,3165,5658,7825,1606,5477,6466,4375,3796,5687,3633,9223,7055,63,2576,6358,5188,5725,7937,2154,8195,845,1695,5992,7244,8173,9152,4078,1272,8997,1378,9123,7743,8670,2717,1400,8160,2005,6344,3977,2949,3917,2832,4058,2450,290,1240,6376,7166,4495,1649,6122,3104,8753,569,1811,3087,2796,2903,8096,1829,5817,6895,8773,9660,4427,7859,4231,6946,7870,1112,8551,1373,1269,6296,4853,2954,5603,6619,7275,2598,7405,606,3059,4602,8410,814,2224,5306,3661,9576,6830,7462,6121,5604,4378,9603,288,9211,5718,258,833,5911,1810,7512,1019,9982,2722,1397,8714,8857,6386,1516,5746,5335,4350,80,8705,7477,8014,3810,8771,9901,1017,1522,2578,5363,8872,1069,8437,5267,2821,1631,7527,5164,9067,2447,4201,2430,3467,3700,6629,5268,3228,4091,6271,8790,3589,2851,5823,6077,8971,1271,481,5599,685,6081,4179,3178,8433,7417,2554,7516,9422,8983,1481,1996,2617,3591,4943,679,1415,2165,8171,6719,1410,321,2184,3343,485,4515,5581,2840,110,9302,8615,1500,2160,2018,8227,9572,4821,8583,4852,9105,2574,732,7229,5827,9705,3646,8185,6338,8856,7660,1446,792,9833,8145,1349,459,1327,7446,8329,5890,825,2428,8621,7245,6486,470,4343,7538,5973,6812,3136,5094,3616,5218,1502,9627,8253,928,6811,3033,9979,7330,1943,7126,7674,8220,248,2508,3833,2103,9743,8525,7070,662,3670,5237,4066,4183,3420,3748,5325,2958,197,5921,9021,5510,8631,2399,5926,4430,4857,8240,8840,4250,6098,6059,6953,3937,2382,2824,7824,9218,5660,361,1191,1283,6197,1930,4934,8510,3041,2426,9868,416,5724,4187,1833,5714,5571,4435,571,167,1121,6431,6780,5723,4281,9385,4076,9880,7878,3291,8202,5997,6444,6500,6831,3947,5919,8384,5978,9038,9737,203,8198,9499,4095,7411,1146,4470,6410,8882,1742,3015,5360,5018,5466,2364,6848,1894,4386,3634,3981,3434,9697,1433,6620,8089,2878,5344,7416,7316,3753,228,4186,6798,8269,5252,7502,5526,3321,4545,3853,4598,3183,2027,113,5937,7936,4469,2297,2746,5500,3530,380,7066,8494,1597,2968,9544,2687,3999,5430,2580,1258,2982,7292,1962,4471,7002,1872,9312,2943,1959,3307,4539,8278,5093,6297,4731,287,4784,210,4588,5927,6255,446,1153,4109,3466,7013,7008,8862,9224,350,5664,1627,283,5082,6445,3888,1873,4365,5721,124,6225,5479,193,3079,5370,5242,8521,7904,88,1651,5709,2953,386,1418,6968,1879,5917,510,2626,1414,1911,9594,347,173,9652,740,8175,6600,4290,9226,968,755,3366,6996,5345,7789,1549,7669,9194,1777,9779,6064,1523,4030,1368,7308,1239,4135,7714,1663,1132,7808,6720,9941,4926,2712,4293,591,8029,56,4432,8078,3158,4970,1488,136,3465,3162,3268,6468,4270,828,5,4669,6743,3548,5747,8706,9451,4082,8287,565,2294,6934,5213,6412,1831,5326,5951,5948,5118,7385,494,1186,5290,7865,3037,7432,5196,3568,1056,6535,9209,7027,6807,7805,2366,9410,7273,1241,3389,7613,9492,8844,9931,1921,614,4558,1599,1018,4720,3115,176,861,2314,224,5183,263,8076,6102,1771,7339,9993,188,9046,7160,4380,6127,49,559,1087,7145,4814,8041,6702,8806,4647,3638,9034,8708,9136,1690,2570,8564,1339,1576,278,6759,30,3754,123,2809,7022,574,5871,3094,138,6485,3648,7106,7827,8209,7262,7423,4466,2831,680,1007,9611,6173,2391,5560,3145,3703,3988,8634,9348,3513,8061,9549,5543,1,2458,484,1472,3632,8949,4716,5248,1436,3010,6589,6599,7260,524,8284,9691,3801,9785,2527,1491,9673,2531,9272,4137,1022,9020,5993,9692,6107,3641,7031,1412,7219,8722,5474,9215,8310,3023,7896,8959,8720,4990,4258,8187,5173,2418,4563,7636,9567,1330,8065,1970,3997,4873,9596,8170,3124,7474,343,4872,5554,9989,1539,6974,2784,2377,8451,530,9800,3663,6650,95,1316,6846,2059,6728,9396,1443,536,9975,2749,4352,1031,8902,6733,6975,1102,8159,8630,838,1111,5356,2017,161,4958,9378,6460,4949,6375,1618,5651,5828,239,6387,6123,5338,5954,9554,5004,8786,5808,7735,1416,3319,8829,7067,3377,9027,6547,2931,7852,9082,7541,7158,9809,7196,7163,9801,8393,7237,4595,7263,8823,3470,7626,6088,4559,3571,2245,5910,4491,1922,889,1011,143,4067,9242,6772,9091,187,3919,2839,4910,6802,1455,5124,6082,3915,3851,8401,3766,3489,4766,7686,5460,1458,8738,3396,9678,7646,2385,9495,1047,241,1666,8471,2167,5423,6339,102,3134,5017,1896,6303,6706,7035,4225,4272,1279,4622,1353,8206,3926,7182,7184,3487,5647,8588,930,8303,9079,1974,2609,5330,2495,3328,7684,6441,98,4762,55,301,6756,9992,7695,5158,1736,9241,1230,2643,5588,742,3664,2897,2677,5616,5375,1014,9654,8769,2249,5455,5533,8208,4760,2457,1042,813,9036,5873,3533,9150,5427,3972,8827,5471,6740,5334,6384,6860,8994,4104,8666,9157,2634,5458,7918,261,9441,9935,6429,115,4761,7732,2119,7934,7399,7954,2067,1406,8093,4206,896,5442,4009,2338,3236,7836,8728,3150,9829,4004,3192,8919,1366,7598,8838,7721,326,5462,4023,1205,6964,2337,2128,4973,3756,3217,4502,6159,9386,0,4796,1678,8405,6454,7181,6854,9684,1848,6803,6193,360,4841,519,7189,1482,974,1346,4446,6701,6850,2794,9204,1998,1530,1769,2237,3186,1259,8314,8968,5231,5104,3764,8371,6434,3003,393,8204,4849,3552,8828,1430,4567,9940,2089,7109,1646,668,2049,4861,9799,3387,9739,9317,2050,2501,4438,2023,7998,1661,7279,2335,8246,3201,1886,9518,7668,2472,4189,8053,1864,8211,6778,9446,6935,8469,3820,3327,7195,5656,487,6896,5892,6310,6198,3522,9331,5019,4711,5387,9855,6777,1533,664,4892,9247,3712,8604,702,7666,8338,460,2584,3190,6318,2825,8474,1759,3547,25,2079,8319,474,5099,4891,4447,3349,692,3603,5275,9267,9324,5952,6566,7980,1361,7062,6269,3408,8911,2700,9985,1588,2855,2535,3642,2765,1570,4161,4612,3081,3823,4410,1803,50,3541,8509,7153,1444,7285,3566,7891,6274,6668,7454,9345,3179,4284,2389,5309,3699,5826,5447,7010,4945,1780,6113,5223,2514,5413,7088,7953,6430,4898,9190,3184,9916,2022,3053,658,8120,1247,1981,5684,1676,9013,9638,7451,8975,9269,5090,7753,8255,4390,153,5615,7920,6997,3233,4130,4049,6520,9229,5101,2641,8611,8934,781,6735,5435,8448,5464,3080,6605,6172,5922,7147,2122,7365,5930,4426,5057,4247,1659,3277,4594,6915,2742,7840,7727,3779,2662,7650,7857,8751,9490,1183,464,5277,6450,2872,9730,8952,6136,8641,6641,6210,6087,3736,267,804,5175,7199,1365,1664,6037,5730,5197,9589,3677,8464,4738,1503,540,2108,92,2556,9160,3210,43,6161,7074,8409,3144,4016,6994,7763,2585,8231,3370,690,4722,2424,5657,2074,9409,5793,9991,7121,6496,7469,5190,9243,7251,6407,5939,9462,5806,5011,6958,6001,1478,1417,2779,3527,6490,3452,7458,5456,8247,2750,5388,5876,158,1061,8590,7046,1700,6873,9561,2845,3903,1496,6137,2860,5912,1086,4689,5452,426,9195,8056,7236,8888,9248,5366,6570,5361,7579,9970,8685,8964,6208,1220,5142,8138,1950,6810,1371,1390,1923,7276,1389,2902,1776,7759,1501,3200,128,3417,7005,2866,7011,1151,6108,4273,6716,315,3832,422,480,1790,162,8272,4151,6415,6477,4746,2945,2755,9569,7312,1611,2628,9006,8644,4217,9137,4036,4085,4836,4481,4659,6791,2462,5359,7310,8938,4295,2865,6841,5166,3838,3103,5071,4675,9854,3842,7115,9953,9314,7048,5020,8388,6062,137,522,3242,1660,9298,2062,29,730,5092,8674,6679,9634,3014,9098,6359,8507,6216,86,8359,8626,5837,1816,3363,1115,8086,5480,9987,9980,8566,6015,4484,3687,2981,537,734,6437,2803,6911,8325,6056,5512,4101,2427,1967,7912,7757,298,5572,8197,32,6180,4903,1982,9445,7464,5765,8841,2402,483,5895,3090,5820,4750,4856,4630,7139,6220,5505,6413,819,7903,977,1819,78,6183,9653,9778,7784,3551,3758,9425,2406,356,1993,5540,5646,618,4298,3941,8696,5186,506,5032,2748,208,9064,4730,4197,6690,7420,5087,9389,6071,1542,1763,6804,9210,3411,4398,737,3508,6149,2230,2658,984,715,8457,8567,771,1733,6648,4572,1855,1951,4574,7608,388,4790,5433,5971,9690,6134,8389,4880,634,168,1528,5303,1693,8031,2847,6223,4457,8755,5319,6119,5362,2674,6498,649,7024,4522,6357,631,6320,3523,5000,5399,902,8541,5570,677,8654,5286,4995,7,1860,4092,1160,911,9167,7550,1615,821,4833,4581,6972,8585,700,4039,2762,5597,2395,1489,1213,1120,9053,8633,5769,1752,2594,8152,3093,7111,4518,7973,6336,3448,7091,117,218,4475,7467,2282,5503,1555,4997,1838,6852,1211,9161,6795,8776,9728,957,1021,1521,8562,4476,9501,3380,667,1692,3312,4459,1779,5700,1512,508,467,461,253,7096,4164,1823,2788,3118,2763,3494,6838,3516,2969,7544,1726,4354,6425,7785,3964,3611,8322,7560,3360,6903,1046,2271,8265,9881,2140,3157,391,2497,8001,5863,3761,598,2534,9065,9401,4178,6163,3125,1668,5416,6647,1947,6898,7039,8225,5632,6995,9553,2403,2345,544,8045,9108,1638,7793,8584,4899,6317,3829,8440,5374,883,2766,3419,4328,7924,3948,9938,6581,1308,174,4336,539,1454,3910,1827,5942,3644,1073,4736,2611,5838,4999,4763,9689,445,720,1708,3225,7047,9232,624,8019,9839,3706,5905,8108,9356,4441,9849,1133,2065,9506,4059,7433,3978,5627,3169,4523,4640,6808,7300,9894,157,6041,411,259,6202,2637,3532,4868,8455,1511,4828,6884,4634,3921,9976,3890,5760,6580,5618,359,528,3106,4989,8869,7831,6844,6480,7323,2478,7745,9266,1094,3296,2898,3510,2689,8366,7861,9546,472,2833,5313,6645,6054,3401,8858,8221,3295,6150,4948,8263,84,4374,1399,2887,3920,1989,8075,3760,3565,7053,1564,2157,5549,8767,1730,8458,8866,8212,7232,4472,4169,6049,7749,1303,5421,4771,272,7679,4639,6129,8122,8729,7707,1963,6687,6971,7426,5582,795,3226,557,3884,8547,389,8479,111,1679,4911,3139,1439,4436,9555,3004,4203,9559,9414,4837,7818,687,7720,7833,2605,2409,605,7393,8426,1081,4337,2445,2721,2751,9039,5139,5924,7032,9636,4220,7845,7781,9781,6051,345,9417,9767,6921,9052,5950,3463,112,9330,4525,7726,8929,2346,5478,7782,6927,7453,8885,8210,2546,4324,151,3392,4663,1427,2107,7601,4870,2811,6207,777,7738,4916,5752,7777,627,3283,6709,6061,4519,2510,5377,2547,6930,6565,2052,4150,914,2685,7710,7071,7751,2492,9784,1311,3546,2143,9756,9703,475,7479,8213,8937,9444,3334,2375,7677,9592,9177,6871,922,2104,3425,750,9945,747,8079,419,5485,4042,4394,9534,7349,4819,3723,8901,653,7651,1701,4240,9722,3447,4202,8245,3573,4211,7628,7286,4065,9914,767,5497,7591,5766,7216,2150,8492,3113,5029,6260,5913,9147,2330,6977,9892,1015,1795,4682,2456,7040,1999,3580,6372,2368,7209,4488,4848,9338,2327,3482,9866,2744,8381,3835,4387,1224,7806,6788,9316,8629,2823,8112,1372,4691,4194,7075,9477,3153,6006,9716,5332,2185,5263,5580,1322,7657,551,501,2468,2593,7688,6697,4610,5996,3034,3627,604,9300,7640,3371,4927,3238,3708,3485,1532,8266,4228,4172,2283,7685,6560,7760,6672,1590,3625,1560,2315,5026,3138,9423,7056,2509,651,72,4696,9132,6978,3206,9289,9828,8881,5131,1074,3747,2734,8977,628,1720,2305,7336,7559,7235,3847,2725,9973,9496,4044,9806,273,8179,5432,9658,7085,5535,8427,8025,2873,1448,2822,9860,4726,8098,7220,3765,1485,8347,1737,8891,5250,7673,3415,5780,4053,5824,555,1226,5740,1697,7087,7950,390,8205,7829,4953,3390,8456,8704,4208,8614,5737,7706,3572,160,4332,3873,3673,5685,9617,1753,7748,7841,6924,6889,1724,9677,7609,4600,4402,5297,2587,6120,5039,9318,3668,1398,3934,1070,7440,3478,8711,683,6849,5337,972,2947,7325,6048,7452,8939,5202,1895,6858,4820,1956,8013,8353,6797,7116,1290,322,6524,9381,803,4316,1940,1208,3733,712,9452,7372,2549,9355,1025,3446,5299,2360,2188,1048,7739,3135,2464,4613,9910,3502,8535,4815,8707,8628,3019,1755,2988,4935,3837,4889,3413,3640,5347,8709,3718,3253,8425,9117,2351,8216,1277,7369,6784,233,3085,8103,8477,1524,3831,2146,9436,9669,9428,927,9307,9936,8399,2421,429,7359,3885,5351,3067,6401,279,2977,7105,1674,9158,7101,1645,3759,6604,9659,4986,7754,5493,8990,5519,7795,9760,7265,6471,6140,2195,2087,1006,9983,8018,9640,5722,2448,6732,5641,2425,3054,7060,2285,3518,8102,8638,4580,6635,120,9240,5329,370,826,4157,1604,2657,8609,9582,7970,4807,2972,2522,8833,9286,5084,7929,9949,1547,373,6634,3517,212,1901,8984,1470,8356,5901,3701,8430,4671,6944,1583,2512,4797,5634,3968,8693,6086,8415,3017,1786,7524,5947,3050,7167,5053,319,7522,8557,2880,7430,4012,2041,8774,1452,3286,8943,6965,6203,1952,8909,1765,7931,2757,8559,7225,9005,3305,7736,2656,5296,3519,579,5185,4988,4319,6983,2038,3250,5241,5389,2369,4604,8787,2112,9252,8645,3595,8504,4403,42,546,7927,5577,5690,5021,9047,4524,7136,1274,1473,2176,5744,5644,4869,4706,77,6984,2243,2148,7367,2135,7390,4950,9180,8972,2672,4451,1215,8161,9612,4968,7135,926,2076,421,256,3958,8954,584,6537,4404,8684,3111,7317,6268,6596,1561,872,4548,5085,2910,5107,5623,1289,6257,2661,7561,6385,9139,5761,2579,1566,8482,5869,7832,6022,1401,5047,3898,9235,8579,1529,6160,8818,7868,6066,3965,8752,4955,8927,9249,9032,1704,4729,219,9771,3197,189,4060,401,6222,6678,9002,9467,4412,8637,403,9460,1740,7094,3883,4382,6032,7333,5060,7270,7649,220,4280,8781,921,144,2915,6621,7026,2859,2355,2317,9954,3120,3335,8215,1794,1385,3311,9301,4072,895,1648,1044,8074,9278,7546,2696,4212,5244,5691,6492,318,7773,7043,6245,1469,5364,2908,93,9142,6489,4043,830,6367,1839,5631,3336,6616,2754,2323,9816,1647,3697,5859,9371,2259,3772,5028,9708,3316,1682,5619,2789,894,3049,8351,7837,5889,1536,2058,6300,4415,68,4793,5282,5903,8335,8178,9119,5909,9044,2563,5702,3569,7214,9795,7217,7698,6693,1824,7532,1142,6449,2078,1013,5980,2782,9274,8087,2367,3440,1216,3222,7354,6689,6913,171,8257,6809,4951,9106,2010,8229,4635,9373,9865,1815,3768,8119,2244,9529,6956,6639,7302,2419,3558,1317,10,3514,6805,8372,434,8930,8561,4874,4126,8713,3000,9773,5787,9434,7756,2261,7634,7990,5527,5086,5496,4106,353,8398,6575,6544,6564,9667,8176,2790,6627,8453,8309,8580,6362,3987,1715,1333,7533,8235,1075,2973,7995,9889,7298,4550,9961,8798,6955,9922,2530,2053,8010,9435,5574,457,3538,545,2325,8390,1598,2564,625,3982,7476,2162,2504,7922,3621,5578,6004,7266,4075,2586,8657,2470,5181,6314,7102,4318,1841,5568,9907,6653,9358,9790,8091,6262,6488,3651,6518,2171,3441,9890,2092,8565,6446,1460,8395,1925,1055,8186,3095,2992,39,3897,8700,3039,7663,2203,4384,2955,2636,107,4389,2485,6845,8107,7683,1425,8327,6925,4330,564,4285,5610,1828,6462,1579,5292,6883,5108,7769,1713,4900,3943,8898,2964,9420,4962,8285,1907,1789,8157,8219,4108,8323,9497,989,5712,4685,5606,6918,8097,4745,7862,5666,6390,8871,4579,8416,7258,4756,5893,3382,4299,9731,5865,5693,8789,4566,6228,1228,6555,8768,1035,4792,5521,6323,7568,4443,7853,6943,8304,2054,8581,7255,6864,7731,5230,3101,5612,7948,274,9379,6497,9439,1662,9353,2713,6017,6688,6195,7637,465,5320,4391,3356,3028,2077,2030,5216,7483,1717,7542,8560,2912,678,8033,7906,2422,7725,2879,3154,4357,1493,9225,2343,8144,2073,1899,4805,9372,3361,9517,5063,5096,341,2124,1264,4656,817,1100,9516,2909,2515,3743,7429,7437,3927,3218,4560,7343,5962,5796,2088,5858,3950,3126,6276,1739,3592,4813,870,3660,9769,6694,9580,3499,2147,8780,7332,9411,2655,3317,3878,5178,4021,8842,694,3732,9724,3624,2914,4087,3496,8819,5713,6235,2714,8008,9711,3786,6980,4261,9473,6890,772,2219,3497,3650,7427,2680,3449,4684,7238,8290,929,8750,7997,6516,7019,7693,5854,5491,3619,888,3550,6573,4907,5271,205,779,8677,7879,4079,8746,4923,4311,9163,9539,5998,6790,8878,5920,4303,4532,145,816,4803,9648,3038,5883,3272,4599,5653,5976,9788,562,887,9169,8030,179,5379,6899,2525,3433,6031,8273,7318,8815,5613,8194,6677,8155,5955,3868,9029,3326,5034,5331,4291,2904,2257,5654,7860,8436,9394,1745,9433,5649,7301,83,6793,6469,8679,9130,1994,1313,1227,9641,382,2279,2252,6952,6661,4121,2602,6765,4596,7802,9598,1037,4496,8834,3089,1005,2295,757,1709,3695,4176,2110,8188,5409,135,6829,9810,7724,7222,3022,660,7345,7089,1402,8730,7303,3608,1155,897,6421,1010,5772,75,169,1961,6356,9337,3344,7989,7353,9820,9601,9328,2265,4616,466,4681,3461,7768,1148,4631,7177,1508,3386,719,8663,6833,2467,3702,2697,4650,4294,1251,970,357,3645,6168,8526,7081,5918,349,2814,810,8620,1812,3622,9507,6427,3456,9056,5328,7528,214,482,2035,3249,7414,9513,2670,4636,11,8374,656,4972,3149,4940,8133,9103,495,2569,9986,9706,990,9159,7095,2785,9271,2037,1563,8864,8912,5801,8987,8450,5556,8289,965,8989,6470,199,6352,1424,8508,6233,3727,5055,6479,7494,675,8039,4783,3285,1955,8428,1126,9315,7073,159,4758,7400,8234,1113,7083,9532,9494,3073,5065,9676,7638,3061,2990,7347,2356,3348,7876,4672,7495,9072,6166,4133,9221,7513,3020,8414,1079,1946,2123,2496,3639,2651,5995,4842,8000,7128,6897,5027,4134,4114,1356,8080,5305,2646,6755,3928,6892,9762,672,9974,1858,2365,1468,6143,6388,2075,1891,7364,6969,9838,6745,4230,3391,1635,8267,2957,1187,1190,6078,6801,1162,2888,6602,673,2161,7051,6201,1232,609,5977,2179,7966,9814,8236,923,9054,2603,7108,8088,339,9332,6178,7776,9870,2858,7567,5729,3262,3794,5148,4373,183,6643,9213,8203,3213,3696,6868,4964,1595,4679,5217,9905,3686,8683,2481,6238,9585,638,5847,6674,1535,8046,4971,8596,5988,7257,5994,6321,7294,3112,8944,5059,8970,962,1128,3674,529,448,7201,1603,7240,3932,9339,9383,3985,2007,3787,8016,6877,2383,154,8732,7622,5371,8027,8701,9073,996,2242,8963,7662,317,3931,4531,1941,5061,3821,4093,61,404,8899,9335,7786,1238,5842,363,4757,2905,1312,4742,2581,1953,3849,695,3462,3721,3557,6206,9388,8512,9565,8655,2876,4570,805,8300,3074,8531,5438,5109,140,8100,9613,9526,471,5779,8062,641,1335,9089,2956,1792,3110,9887,917,6630,1619,5030,7461,3263,4439,9742,4996,2141,4905,4236,7069,4283,31,9821,6423,7562,15,4170,333,5463,3501,7295,7803,2980,7422,1195,4888,4127,2328,9074,8488,3227,1804,7554,4442,1926,2438,3869,8892,2066,8326,5257,4431,1966,8826,8895,8132,8376,3240,5264,9911,2339,4322,6067,7444,9606,3567,6704,5083,6878,2175,1219,9102,1914,1865,1596,6293,1403,1960,1573,8875,3725,7886,2653,8665,7514,807,8283,778,6046,3235,9978,206,9958,7548,2561,2488,7664,619,5172,9600,4583,5908,7939,3922,9918,7971,7771,4244,2519,5569,4835,1846,8597,7180,5965,2493,7987,4620,35,4811,9313,7612,709,3971,3040,3828,6779,9037,9250,1807,6433,9657,5022,1178,8099,8117,9454,3076,2552,6534,2951,7460,36,7358,7967,994,9070,6019,5054,8608,8900,364,5192,4089,9867,8733,8926,6058,4625,1936,8177,1821,2228,2507,8874,7596,1592,6118,5872,3881,5304,397,8816,884,3839,1621,8877,5652,4167,8168,1167,1707,8966,6463,7788,5193,2950,477,3237,9134,9075,1068,2096,8550,3852,9920,9823,4845,8636,3813,7843,2630,3814,5739,3874,3597,6514,7639,2919,3035,959,3767,6308,6377,6025,4642,71,4866,4096,918,2333,4692,3729,3830,8932,9010,8400,5891,3476,1447,7431,4492,3671,1150,1345,9476,686,6936,3306,260,7585,5369,3367,898,5045,1965,6187,9088,6582,5222,4782,3836,8466,7750,9807,1099,4034,7755,5037,8333,444,4584,5422,9025,9856,4399,4341,4210,7984,7615,1797,2069,1233,7775,8686,3388,2106,4117,6003,8441,8113,5727,3889,5878,1744,5595,9227,8498,5289,8928,9939,6103,7500,3160,3845,5931,9251,2289,6869,8136,869,7304,4326,1379,5097,9896,6284,5283,9329,4420,9124,4175,2565,3180,6821,2117,1336,4461,9076,6380,2214,227,6378,6556,4632,7872,6115,1409,6836,1877,8230,9505,3916,7866,2933,6675,6008,7132,1256,6874,2537,7914,5214,8532,2690,6667,5945,2996,5333,2817,3549,3302,761,5906,6435,7581,9735,7946,2026,2529,6760,4274,7137,9398,3043,6938,304,9153,842,2863,5897,2649,9395,3350,9292,2372,3219,9798,3121,6342,2852,9602,4148,1909,4143,6870,8667,5285,925,7715,9702,7015,2322,9009,4070,94,3893,8757,2443,8662,8153,9750,6901,5983,5935,5706,6309,6615,910,4086,5732,7653,3505,5925,3299,6212,2000,6680,9181,1214,3455,8675,1159,9802,8556,5703,6586,5270,2562,5486,8958,7210,6806,5076,4587,3776,3574,3044,3542,1758,7623,1939,1748,3659,3362,5392,7168,5414,1067,8649,6334,1832,608,33,4166,3354,6264,9681,6124,3260,5381,9853,3994,4514,8143,90,3782,3755,7054,2407,9897,2397,3945,9447,7021,4517,8116,822,7928,4946,4321,1203,733,2144,3252,1197,8876,348,3429,4165,5586,3105,6285,4064,8139,1347,9502,7611,6101,9990,8887,330,593,9487,3011,3137,229,2781,8974,1475,5642,2353,9095,7342,3680,9333,8889,8156,4801,9530,9642,127,3423,5476,7443,7226,770,5007,8659,6947,2709,3556,8694,4026,7820,5662,1028,9453,7590,5249,2210,5677,5489,3726,6624,1363,6557,5697,5058,54,1783,1036,3684,2929,6265,8690,7718,6950,1419,2961,6598,8489,8248,9836,4855,2201,969,4864,8528,7472,6096,967,9347,2352,4437,2032,8123,7425,2550,503,1852,7306,420,5049,7531,9891,8172,3863,617,8718,4759,7375,1942,8846,948,5674,3909,3300,9577,9320,5607,9858,3553,8307,2625,8534,9342,886,4506,2256,4120,9297,5191,7697,6751,8286,9883,4823,8193,6493,9419,6487,5397,9548,1979,9509,4877,9188,3901,5051,4001,4773,5145,1980,1008,5266,986,9118,3287,6324,6105,5095,1315,1266,291,4406,2917,5874,7871,6640,7186,3606,3175,7371,2884,5771,3529,5881,9817,5836,6549,2989,7576,8485,4834,5805,2080,9774,2311,1609,7246,9895,6822,2169,4768,3860,8037,6258,5547,7717,8467,4724,9873,3905,1057,8915,4010,6280,6696,780,1931,2379,7162,5418,9736,3056,5544,8913,2619,7509,166,4256,3269,9850,9045,9557,395,4232,6532,9721,9334,7911,4307,1354,2347,3620,9362,1916,815,8470,9093,1675,9042,1728,8610,4363,1222,7547,1515,385,180,9479,8054,5353,6673,2618,3292,6442,860,331,5149,4649,5832,3351,8379,8600,985,789,558,707,2019,1023,8083,7261,1089,9885,3769,4755,2856,1343,9714,8743,5315,7374,4251,7694,1655,1985,155,5441,4359,1093,2613,3024,4141,9966,8681,4774,6511,7144,6254,9291,53,468,975,2506,993,987,4180,4667,1548,9780,6307,7702,9608,1710,5468,9208,1050,6085,8524,515,525,2952,5162,4158,7947,2892,8850,3789,9466,8741,9486,8624,5407,4660,1337,4084,7156,6703,5853,4351,296,4747,8408,7175,6090,3173,9438,442,3777,4455,230,5879,2582,5048,2387,6691,3707,2806,4340,3953,2444,699,5147,4966,3871,8719,8055,1185,9323,3643,3728,5596,9094,1856,950,9063,550,5851,5579,9170,2704,3209,8196,6715,9191,3318,7159,1908,4577,6875,6684,3091,1874,2212,4764,9090,8268,3359,4919,3818,9512,295,2846,7582,9550,9327,1572,8618,7419,2841,3172,2682,2718,2277,8417,2935,1551,9484,5552,9845,3097,1325,3824,9581,7218,6967,8617,5074,1052,6241,8736,1273,859,6116,8731,4181,7148,4254,384,944,3524,7475,1207,3652,1193,4878,5844,4421,3199,9888,4664,3896,4987,449,8036,5169,1677,4781,2344,7213,2173,8831,300,6026,5969,3128,6999,998,1291,4100,6533,1163,6623,7728,3585,2380,3583,5156,2747,5602,8502,7772,4493,9707,2477,2255,2844,5322,5695,1267,7952,9696,1242,8907,8821,45,7885,3052,3570,9934,3578,6888,8429,3480,2494,2287,7508,9859,6764,1480,2538,2922,6005,1196,8999,3618,585,9568,2541,4309,3587,3944,9921,4890,7821,9749,1301,3590,1161,8106,6426,9143,8073,1723,6027,1376,682,430,6739,723,6631,9370,5126,5831,3936,9019,823,7501,3241,2461,2011,5506,3385,6727,1644,871,294,4035,5956,9273,577,9340,8141,2608,3083,766,4417,6353,3995,1527,2178,2759,5501,149,4424,4473,3100,5753,6146,6507,1741,1449,548,5829,8914,9738,4315,4433,1626,2705,6186,7855,8712,1184,2741,5492,7457,4098,9310,5936,8282,561,4024,9560,797,3232,8859,8627,4516,5168,5081,3109,2701,6345,7603,8394,9994,3058,7466,2862,3290,4840,3692,4562,6277,2916,9933,2758,9874,622,1254,1623,5137,5803,6002,116,6104,3854,2324,701,2694,595,6744,5710,7741,7977,7077,6800,4648,443,570,7791,4234,7574,211,8698,4641,381,2756,3196,9643,4883,8137,1541,7991,1465,2740,1198,3375,1727,1306,1767,9782,6229,7556,818,2258,2420,6070,2432,2999,9,170,5635,4112,8032,3657,3698,7593,3656,2802,7504,3270,1919,2340,6817,1210,238,5002,2221,6176,7951,9293,3762,5741,4906,5429,4817,81,7893,590,1147,6548,4846,8140,1201,4540,1814,6583,3717,5406,2566,9421,1288,8625,7170,5985,7894,8569,4077,1897,9950,8836,1499,581,1293,951,4611,4458,3900,119,1066,2557,4116,5467,4334,7368,5135,3231,7945,8134,4687,4787,1016,3653,9096,509,2676,6043,9575,7851,670,6962,5504,1650,3146,9609,3471,4520,8669,3404,526,1182,1487,3251,9149,195,6530,7994,2390,1652,1734,3993,3822,1847,1883,9893,6439,5953,6865,5014,6184,2664,9468,2675,1438,5916,7730,2615,2229,2991,3075,4329,1062,9525,6941,3477,7198,7518,8870,8059,9622,5035,3224,4422,1461,7193,9687,7919,4799,2441,7838,3740,8085,6073,3809,1045,8244,2293,2121,2,2800,7955,9061,7003,8403,9765,5470,8002,9151,6603,7536,3187,3164,4287,1107,3617,9754,4003,697,9547,978,9078,9558,5861,3724,646,3598,8832,9146,8697,8447,5288,163,7892,9947,8651,2987,2003,1694,1912,9168,2941,1719,4017,913,7900,4267,6083,9625,1878,2911,8011,1495,1538,9729,9523,5886,2542,4534,1586,3202,134,9189,1388,7976,266,769,2446,1976,7221,4975,5161,1990,854,8640,7921,5834,3554,8391,4743,3472,5386,5975,594,1725,3984,2021,7282,4830,1544,5391,3072,4501,332,1525,6505,6079,58,1640,9129,9827,7635,7588,1098,2627,4204,6417,4242,4140,7391,1369,6366,8301,7388,5159,949,4938,9048,8048,3503,4885,876,6776,7703,1209,7104,4825,4704,2635,3185,6291,3990,1085,7387,8130,4425,7917,8071,7488,5163,1658,8647,1686,6561,7141,6931,5841,9030,4824,4222,8635,5984,7076,244,7558,6363,3734,46,6839,8646,7563,8363,3798,7328,6182,3313,2575,2808,5393,669,7397,6559,4097,8797,560,4227,4767,706,1497,9437,1665,9217,866,9199,741,6867,4125,3077,1189,7277,1680,1775,5866,5845,2503,4213,369,5064,1078,8443,4379,5671,3221,1844,513,9777,3460,5720,6501,6957,8612,5566,6954,6069,7652,9631,5179,8744,6162,1199,148,9842,6189,8063,1280,7719,5683,2109,7956,1292,2669,4504,3526,1300,6211,5235,1175,5609,5867,3198,7183,6669,7403,3166,1520,2151,7155,760,8129,1558,8465,7604,5559,8602,3581,2966,5758,1746,7969,5991,7932,6824,4718,3875,729,5638,9112,3451,9674,7774,5446,2408,5378,4364,1581,9964,2539,3426,9214,6682,9309,798,7864,620,2882,4068,6453,6145,9919,1610,6721,4847,4323,7898,2736,5010,156,3132,3561,276,1593,8081,7299,66,1504,6065,2804,2361,5426,7410,8517,486,600,2597,9299,5898,3369,9482,3147,6783,9981,150,8368,5860,9463,5402,7709,2199,9822,2149,502,3637,6900,7566,7848,939,6742,4727,3368,9819,7463,7700,4860,9276,9732,3275,9535,7110,5254,5454,7441,9748,7629,5862,8418,9725,853,451,848,5617,1796,3744,1026,5857,9869,5754,4142,7884,8778,5530,1000,9552,8299,3535,7205,7311,9100,9068,8520,9179,1328,6665,7202,5088,4780,6397,3636,9270,3940,3693,2415,3709,1492,3856,8481,4259,2220,271,7272,4575,8688,8589,1749,3859,5228,2921,2172,3716,2396,9303,2588,9478,8539,7941,1166,9135,3715,277,9193,9205,1374,7778,9903,9403,6855,488,2944,961,9197,5884,9216,2590,9430,6966,4638,9618,4229,4372,8434,9515,2907,7421,6577,5788,2553,1689,5110,9028,6940,3140,885,1688,1453,6152,9172,4218,9246,2850,3188,8861,462,2500,1721,3720,7122,4818,8358,282,2416,1968,8661,4111,7797,890,6484,4568,6473,6379,4897,4136,5233,4474,2631,5119,5495,8946,5990,1450,7150,2813,70,2591,1589,6789,9035,724,2102,2975,6023,4069,7580,7394,8839,1285,7030,5350,2997,7747,4744,6147,8028,4393,5798,849,7406,9121,5262,892,8799,275,6963,946,2864,5621,9060,9145,4155,9851,3418,4241,4673,2772,6762,5750,7357,3068,1253,4633,5259,7012,4320,2417,8339,9057,2647,2829,9126,4652,7224,3393,1413,9412,4188,725,3975,9187,3961,7505,4224,6091,6248,1348,237,1837,3239,4282,8406,4408,1798,6914,2733,9011,129,6948,478,4555,9587,516,5372,5600,418,5357,553,1001,7549,726,6851,8392,9464,650,5532,6261,2928,7124,6593,4339,2460,1820,4626,5680,5236,2668,6726,7752,2743,6246,9864,1080,9174,7269,2843,6843,7049,3904,8748,8361,7643,1584,2830,7790,2979,4257,1654,1083,1377,1600,64,2938,5238,9912,9826,79,6494,5561,200,2440,2374,7742,9349,1351,1617,9418,9185,9424,2967,4147,8692,7648,2869,7442,8313,9162,8812,3301,3304,8237,8740,976,9306,7874,1408,1038,837,752,6478,9932,9399,899,4409,201,8558,6259,4644,2373,5144,65,2250,4714,6774,5940,5626,6196,6578,1483,881,3071,1125,7632,6068,414,3949,8296,476,8756,194,303,4554,6270,5114,1747,2429,7583,7503,6138,7675,4974,8793,8623,1845,1223,3750,410,4536,5365,328,9508,178,1471,9107,1735,3973,2889,1457,8595,376,3229,7630,5232,5781,4933,2639,956,5174,7335,8452,2767,4376,1571,5260,5558,6142,8642,2263,919,4697,9220,8835,5062,423,2870,6316,2051,4306,4216,2604,6305,9231,2644,5770,9704,3365,1484,3631,3122,7346,3214,3773,504,9012,4617,3892,2329,1140,6299,4887,4173,843,6692,8192,5040,2770,1466,2760,3412,9599,3867,916,3032,5425,2318,2091,834,4032,447,2986,6676,1964,7711,7863,2435,3959,8355,1268,9131,3156,6240,9405,3531,644,2118,2174,931,3298,8519,9875,9766,265,5050,5629,782,5128,4552,4733,5398,615,4507,2386,4264,6724,3274,2623,1772,9206,9727,2015,7117,4928,6111,4286,2993,5134,8923,5716,5246,3029,1620,2251,9144,2043,652,2826,1486,4370,5276,8940,935,5408,7978,4576,6301,523,2923,4917,441,2331,9397,2166,5751,6181,636,8770,512,6100,4565,4490,41,8545,1781,8784,9862,616,4922,3308,1934,7112,3960,2963,8960,2849,8493,6885,5383,7993,2540,9688,5835,3509,2871,518,7376,9182,2208,708,415,8544,4465,305,1509,473,311,7119,190,6221,9764,293,9363,2071,7097,4710,5670,7478,4018,3215,5295,7605,5111,7940,3791,1467,7386,8232,1294,432,5459,4657,1490,1902,9924,2489,7681,6973,4791,7800,1699,846,6368,3778,1352,4132,517,213,1249,5312,9184,28,3880,6785,5272,6592,4936,5776,4978,6912,5630,2180,7672,1344,3861,716,4377,1152,7212,4245,9166,8035,7822,9759,785,2978,7165,7140,5742,4327,87,2025,4538,3230,520,1818,8292,3540,7268,6939,3956,2555,1882,9295,3243,5584,6610,800,4007,7627,7204,4802,6024,1718,4865,3998,7881,6775,809,1053,3844,9125,8996,7962,34,7459,6597,8311,7434,9285,1382,6290,3324,4606,5783,6757,2098,3247,5734,1088,7438,5009,6503,4054,7799,2264,5757,1667,3865,6642,8369,1992,2528,5068,9679,1407,5633,5484,7064,7498,8275,9574,1334,2222,6656,4624,3913,3155,9628,1629,8364,1049,7271,983,4732,9960,8965,2068,4776,1978,4637,8783,7380,9948,1456,7902,3347,8166,1582,8978,4944,4875,5376,2126,4008,1801,8182,4694,9844,3208,5155,9825,7573,7618,1141,7529,903,340,8759,6646,3678,9239,378,1299,8128,8069,1076,9376,8804,1808,7382,5265,4138,2894,7455,6568,4308,5536,1331,5395,3084,1843,2083,6278,4703,323,1051,9661,142,6383,5070,8044,6710,308,3969,6606,9288,6499,9175,4690,8024,4547,9886,8543,5967,5106,991,7569,6060,2901,2008,82,3713,6094,6723,9040,3512,9202,4489,3098,6922,1513,1806,3577,6253,7908,8573,8809,9665,1788,8249,8643,8791,8601,9786,1859,8538,4932,312,2198,9148,6292,788,1625,6382,3444,7436,1302,8925,2629,4103,9997,8332,1995,1543,198,5511,38,6663,3399,4450,8294,7766,8591,4146,4591,4467,9245,2723,9326,3979,3816,5764,8956,2516,2306,2127,4844,9753,9882,2213,8553,6787,8542,7676,8009,1002,89,8497,6985,6708,8513,9671,2455,835,5077,3339,3205,8411,7253,9384,8678,2567,3211,2799,744,2711,8460,5033,8486,4593,7687,904,8038,4344,4739,8745,607,6155,6029,6369,9808,5380,5516,8252,2867,223,6991,6244,6475,7296,3911,177,6349,549,1072,1545,588,9305,245,2774,2511,2729,1358,9488,4411,9715,6057,1849,2269,9588,8387,1517,7058,4939,2090,710,8522,8424,2732,774,6528,3676,2414,1880,9520,3826,7539,2792,1800,7915,9751,1435,722,1437,4002,9413,7746,2334,2013,2473,4011,3962,5810,9178,4717,5284,9831,1784,122,538,9458,2196,4981,6664,9352,6773,1885,5888,1944,6908,6039,8518,6986,4614,5273,5907,9595,9408,9003,3117,8396,7404,2985,6840,9675,6574,3722,2309,8104,2401,9469,8297,1876,2410,9633,73,8687,635,2835,8022,3042,7037,7779,1117,671,3159,5453,1422,5622,5513,7942,1633,3107,1192,4549,5797,1805,6242,4346,5003,146,7080,9925,9474,2350,9263,3704,7206,2820,5877,5846,6422,8407,2706,4623,8536,5614,3989,436,1585,8344,7713,5592,7289,4521,1137,5785,8491,7659,491,7482,7614,3,4445,8305,3691,5816,5448,2836,5056,6981,1802,2158,8181,5352,4770,4335,5525,7492,5880,7986,1871,6842,8262,3384,1429,1200,1869,3719,8980,355,7722,3906,8064,3248,4276,2260,8739,3811,1188,1305,552,3912,8320,4296,1329,7644,6373,1685,3486,3069,8985,731,6370,9680,2927,9733,7965,4462,7964,440,375,8251,3030,9951,3593,9360,8578,9533,5157,9498,4500,5006,9996,9258,2971,3742,4778,6188,9884,2899,9984,9700,7587,1510,9007,6044,3738,7661,1029,1954,7762,7334,9283,5972,4831,1275,1691,8917,3628,3005,7521,3992,1519,6670,7835,5069,6579,7133,2946,4239,8316,8592,2737,1622,6354,6231,6835,6330,3127,7439,912,8785,5226,4073,681,4423,9768,9431,2769,7068,8380,6018,9341,3711,8315,527,7600,8200,336,3879,7826,2684,5768,5601,2517,2962,1613,5102,6289,7787,1041,9571,4071,8586,325,938,7025,1905,1949,8050,1933,947,4508,906,1756,6279,4918,6595,8853,6932,5733,5234,4416,9699,5274,4131,1164,4397,4029,8422,4265,6110,7656,8873,6237,7044,3607,6075,4383,4301,1928,7489,438,4347,3682,8475,3309,5899,6758,1034,3016,8916,759,5791,4914,5023,5420,2060,4477,1286,6717,5933,3297,231,2029,6272,2918,2505,6700,8619,2533,6750,5589,5553,5689,9744,6506,4055,1984,4546,9789,5643,6432,5243,7770,6718,2883,8908,23,7844,8605,1281,8540,3130,9713,9551,7834,2837,8468,8514,3666,6214,9456,6333,6509,6263,1350,8880,1506,7281,2730,6510,764,5321,6028,4118,9668,1637,5080,8105,9630,6553,3857,3576,9141,7491,3749,2571,5855,2231,2055,3267,1988,5545,2116,8801,9255,6622,2848,5667,878,3381,3331,832,2797,9908,2810,3428,7259,3273,9605,9717,2273,3453,7796,2163,6080,3737,4544,4769,2177,4839,6038,6009,2707,8905,9957,1131,3007,3400,8438,8843,4163,5763,2048,3877,5211,7813,754,7996,4051,4020,4651,1405,9392,5745,4062,139,9281,8057,3435,8695,108,9400,9031,1236,131,2930,2925,8015,3333,6458,5774,7130,8094,252,6089,6876,492,2692,2313,5245,621,2936,1932,1097,7456,3803,1608,3410,2600,7351,9450,4851,8222,4260,4619,6326,3045,7497,1888,9406,8727,9847,9472,2028,4094,773,7036,4366,7231,1669,2959,7131,4487,787,852,4304,6681,4045,4177,9261,7050,9755,4185,1255,6698,7326,8979,3588,1432,9238,6072,3168,3946,1295,5031,5308,7712,1768,4122,1095,3600,1181,7450,7520,9597,5133,934,8480,5946,5368,1145,6213,9099,640,3279,7882,9368,5150,62,5394,4879,7408,5541,2254,2236,7899,2304,7888,4362,8115,2197,4027,979,1546,377,4483,5537,9962,4360,8072,6916,3792,1630,6970,9344,2559,7179,9084,235,776,7187,9928,8935,2139,7486,568,2298,6989,1854,735,1176,6348,6440,1904,4896,1957,3070,4901,1836,8658,3562,2771,5968,6013,573,8922,5786,9624,2290,4381,5450,6099,6191,6374,4182,8360,5507,4812,7241,6585,3281,4680,5229,6522,8047,8121,9254,1580,3341,4862,1136,5256,4497,920,3459,2610,3855,2310,645,6546,1553,3163,6361,1180,1221,9087,8382,9837,9449,3579,2120,8386,3473,9016,3065,3923,2223,6128,7001,7125,2359,1537,458,1122,8020,5705,9562,4529,9591,9857,7487,8546,6609,8127,8599,7975,8735,22,7850,4037,3310,9001,1130,292,7737,5620,1641,6275,8639,7290,1887,7154,8101,4967,1459,6459,7814,1927,1893,5915,840,3088,5008,6205,5655,334,3195,5668,936,4317,940,3685,9004,8897,5591,4809,9726,2354,5778,2695,1910,1355,2296,8404,4052,1282,2276,7331,6685,6482,453,3536,8124,9351,1395,7313,6394,728,1451,4788,3902,4263,4597,4191,1853,4582,6657,647,7690,3817,2136,5731,1938,3427,2002,246,9573,6671,8516,2475,2926,3026,5410,6834,7960,648,5762,9843,5123,2280,9812,130,7692,6872,1986,3963,3421,1060,4528,6649,5773,3064,915,5269,1234,3488,7889,469,4728,5624,2248,7943,9086,8439,307,6862,9969,2702,299,2100,7448,1105,4843,5914,7207,2463,1204,3745,8896,48,9481,796,3468,3872,1556,7020,9470,4503,5136,2292,6036,6590,5777,7849,5341,6959,5679,7578,234,2388,2442,8660,8988,8950,9321,8503,4737,2486,8261,1082,2686,8906,8226,1033,763,2753,5072,4395,3332,6666,4159,5563,8951,3610,5696,6035,5382,3464,4810,7571,1118,3481,1636,8884,1323,7764,5293,4047,2341,3843,2648,6906,4468,1751,4947,543,5885,3303,4080,8749,1003,4061,8764,8552,74,7761,1143,6331,6347,6050,5318,5961,8955,1217,6084,9367,2266,2064,5339,4464,7517,4723,5665,2034,844,5852,6236,1915,4129,2633,2130,5167,8805,8782,5201,7084,4288,4893,9540,7473,806,5461,5887,5825,4827,696,2632,8699,566,7169,4920,6705,1020,9503,3457,9382,8154,5189,2719,9723,6923,2893,596,3951,4765,8271,9977,4908,6365,8375,3887,7127,603,9824,249,9968,3966,9256,3544,8918,8777,1340,9377,7034,676,9432,5663,5140,101,1287,9493,6504,6933,8656,3604,5310,1149,1091,601,6341,9015,3907,5221,9685,2156,6951,582,3605,7188,2984,5738,4775,7384,7624,368,1479,8264,7933,2857,5342,6131,799,7082,7680,8218,3848,4698,6033,2715,4452,147,9944,352,2191,5868,7597,6993,8306,8293,5170,7234,2206,8527,5856,3245,1307,6420,2683,6823,76,7228,7370,5708,7377,2433,7963,2040,7988,5636,9500,9621,1225,1156,7823,762,3688,8779,7577,2241,4237,1738,7923,5042,3679,1391,1550,1411,534,6683,3942,5694,7379,8849,3177,7227,8501,7340,1324,2274,9797,2638,320,4735,5091,8023,8348,9848,26,7023,6313,9955,4361,5396,2392,2202,5431,7194,8207,1396,933,7816,450,8005,4144,7079,3167,2303,2645,5728,3458,7985,6010,1318,7617,9898,2186,5529,9666,3730,8820,7250,3416,8962,9212,1123,674,3771,9720,879,1935,5208,1862,6302,2498,9649,6007,2439,7309,257,5116,4279,1364,4609,3402,9906,2745,2384,9972,693,5989,2728,505,4677,1673,3329,7599,7264,7348,7383,5098,4695,7373,6312,1716,2960,5195,2573,626,9275,8650,3474,9359,2601,6753,9369,5180,4646,7961,748,5384,4702,6112,6465,7801,9971,2568,7157,8796,9104,2752,5411,9237,5103,6554,6266,1642,5437,7551,6917,5548,2739,8378,324,2885,6769,6328,8717,2267,1743,9471,2780,4924,202,3424,1526,3430,285,2816,8613,4353,6521,232,901,4509,6298,1977,4621,1384,6736,2937,6350,6880,9683,7114,4751,2358,3278,6063,4912,8003,3914,8298,6224,4355,362,1024,5141,358,4753,3795,2393,1202,7883,8058,8250,4699,9138,1554,4979,5711,9113,2145,5673,5227,5445,8758,907,6360,9527,2614,4345,7979,6894,8288,8496,7407,4456,346,8763,8328,3784,5472,9570,891,3800,8803,251,8149,4629,802,6711,4937,6502,6770,5692,8478,5792,980,5814,4463,8090,812,6523,9230,9033,8760,6771,5494,9287,2336,6644,2454,2232,5327,4235,5987,6396,2526,1568,309,427,6998,7606,9156,9524,2209,9459,5575,456,2134,704,7586,8668,9000,9059,7278,5782,1696,5564,5515,7972,4991,6154,7327,4571,6576,1799,8190,9455,3815,6319,399,8331,9228,2423,4952,1498,175,7999,1875,7378,3694,7701,4909,5843,6381,3862,3119,9647,532,4300,4913,5688,4090,9832,6167,1577,9361,1813,2906,13,7134,6491,9483,3256,1177,7284,2654,222,2204,7557,3129,2246,6513,4088,306,5016,5538,7968,4748,8365,2592,7017,181,9639,7647,5557,1071,9663,714,2731,9929,2548,6907,7248,3537,5255,6752,4262,6737,9109,4139,1656,7018,8817,4313,6053,1578,7589,9871,408,3929,7164,6816,4749,9083,9077,3397,2793,6355,6174,3373,5802,6942,1218,8147,6340,8420,703,2624,2939,4512,4356,5115,3812,1119,2934,9610,5143,3405,3783,6419,8814,5440,4022,8021,9357,5669,8837,2020,1575,1569,6929,1084,5281,6097,1420,7858,6294,9111,354,1477,1229,8007,407,7792,3246,1850,841,5749,9664,4993,5528,5199,8533,6662,4226,6428,5508,9619,7935,3013,8982,6158,8802,3560,8931,6286,1687,6652,5555,2316,1381,824,2284,1634,7243,1706,8863,392,7734,8721,7033,7307,5129,7670,2764,2376,9710,8302,7767,5726,6315,40,1822,9564,344,4152,8682,3108,7523,2326,9155,3358,3376,5316,6170,1173,6400,541,665,7607,3986,2193,5112,6343,7671,5550,9709,637,831,8574,4513,2815,6538,7297,6351,4569,6416,1534,7696,1168,4564,6443,4145,8385,1681,4198,6979,2194,8593,5648,4401,9543,4405,7239,2596,4942,4278,9537,6281,4154,7525,9563,4957,437,2097,3261,2211,6424,8689,689,3171,8370,2319,4348,5154,5790,7324,7901,6902,5594,7974,739,5390,9120,5698,3131,4772,9244,338,8725,4277,4985,3031,4686,5171,6226,9917,2095,6014,8346,599,9280,9080,2868,9050,8174,9186,6194,7983,1263,1065,3181,3647,1762,738,3099,9416,941,765,547,1174,7360,242,9644,7322,2807,1657,4829,9741,7890,5520,7319,9590,2616,4603,1607,4200,6536,9294,2622,4449,7355,85,6794,1826,6436,3582,2105,297,24,2890,6052,2589,1252,3006,1764,8373,1973,7642,8582,7099,286,1386,1770,6539,877,1297,1169,8070,3626,8792,2057,3500,7142,8824,7028,659,3539,2405,9448,4795,2332,1139,758,1866,6418,4041,6256,5819,9133,7828,327,5300,4289,3976,856,1628,5675,7293,9536,745,1404,6332,2599,880,5219,6130,2827,7810,7176,3613,2084,9646,2164,3528,2349,2101,9014,3894,7905,6047,3337,6747,2738,9154,9876,2348,633,2487,2798,8280,9579,2708,5870,7337,2312,4705,8142,493,254,1559,5839,3938,1284,1732,8151,4149,5982,7014,8109,8851,8228,5465,5336,9183,8499,3774,2226,1722,3454,9171,1861,3439,8813,5261,8852,9343,383,394,5686,5929,9712,5928,5013,7733,2159,4607,7009,8291,6020,7471,3840,5676,4930,8432,9655,4715,7029,973,2113,9364,1507,865,9058,3808,3612,3614,3584,9718,3395,3001,8277,589,9776,1975,8324,6781,1165,9393,3151,2133,6761,7113,6234,7415,4915,2247,1276,8449,5205,1785,2115,9607,4128,2268,2932,3665,7716,4858,8004,3258,5451,952,2371,3216,7178,1892,8114,6165,7341,9740,3484,2342,1766,3330,9279,9830,3930,8867,1632,9670,900,9583,1705,2480,8068,6754,2773,7815,9236,7925,4192,6818,4392,3790,3445,4886,7305,753,9041,8505,4535,6731,1809,6000,313,613,5138,862,1476,97,5943,1124,1101,8848,2558,3257,2583,7691,262,4712,4779,4921,1116,521,3594,4371,100,6659,1671,9092,365,1246,851,3266,1900,691,3525,2320,8652,6,2270,3048,8191,2659,5659,7537,7910,2476,20,9259,6562,5224,225,3918,9852,7830,9196,8095,9793,1917,5401,4976,7191,3850,8890,7321,1714,1138,9008,6617,1103,3294,6093,6782,8463,2768,3846,6139,8337,567,932,9164,3746,1341,268,417,7610,3785,3450,7413,5207,2413,3731,8737,8715,1562,3021,9268,2137,7352,6157,7655,9165,4419,4215,7389,2398,5089,2861,106,4533,1997,7877,9192,6515,5565,3967,4,9745,6658,7723,8653,5165,3834,6863,3705,5287,2621,3662,2532,4505,9545,7445,5587,2842,3925,8948,6395,2449,6928,132,2940,5122,8243,6249,5024,5637,3394,3807,2663,1171,4153,9923,2063,4666,5608,6414,7555,9747,3092,7412,2187,2072,4407,850,1835,9811,1494,6164,6011,9915,4665,6283,9879,6738,4794,8622,398,5212,8006,4931,2001,7042,2834,5314,5639,91,2524,431,1639,9457,6179,864,3282,2671,3051,1840,3431,4099,2874,5025,6767,7817,1778,5373,2698,7565,3443,3672,8664,2288,6847,4994,1027,5152,688,8279,5204,2691,5073,8577,9909,2983,3658,4253,5206,6092,7200,5079,99,4578,4005,2499,8530,6476,5473,9128,4050,1474,6910,1298,5044,7329,4526,3008,2081,6699,8603,9586,7338,1624,7465,953,3827,6399,4961,7172,4854,3675,4709,6405,8126,8961,2886,5900,379,6392,8795,2262,19,2891,9222,4786,7957,1030,7041,1868,6227,6722,5822,4249,8765,5184,576,8766,9043,4826,9284,9792,7875,9319,6364,7052,3409,5542,1134,1043,4448,6438,9988,4123,7553,5419,2560,6106,5100,982,9304,9346,6074,4325,6976,8367,610,8462,2400,746,7361,6749,6204,6569,1729,7621,4248,435,2009,5833,5502,6637,945,963,9614,1426,7211,4460,141,8336,337,3615,9097,1260,7658,8515,5412,2693,8352,4683,463,5200,7320,7409,9942,6250,2965,5203,9926,6287,6398,6406,60,9787,3996,5562,6335,3895,6542,2082,2726,3353,5864,4333,7287,209,8183,2233,1937,2482,5850,5628,5121,2545,5804,9110,8446,1889,7078,4434,2152,9101,3493,9519,3027,1442,1370,2812,8845,1338,1653,8146,6451,247,1129,1463,182,8671,9264,8811,3689,2200,4246,8092,629,7118,2434,8476,1972,3403,8648,2913,7705,7315,6909,67,1314,8276,5317,424,454,7507,4895,9840,4480,221,329,8886,1004,642,3841,7396,9429,3970,8199,1711,8575,9616,9116,3586,6288,4902,6594,4894,4586,3543,5789,5815,9863,8868,5125,9426,335,8238,57,874,5812,1342,8973,8233,16,6171,3882,3886,9023,7602,270,7045,4400,1039,6455,9277,8570,3148,3690,9805,4816,207,4498,7038,1602,1392,9440,4160,7930,4585,1890,4429,2595,264,8164,8754,5938,5355,5210,7812,6402,4806,2114,2786,289,1683,351,2192,8702,3086,6893,5132,1257,542,5340,1591,6199,3498,9542,7944,6628,5650,3170,5800,9998,2240,2378,6904,8040,2299,6135,3018,743,8397,2666,9695,7794,5949,5807,8587,1237,1440,6526,5354,8242,7916,6853,9791,5840,1684,4056,5247,4553,8423,2775,6144,5385,4209,4956,6820,2924,9511,2451,8673,5704,5239,5153,7280,5999,4645,4867,2474,6327,5583,8312,4013,2484,2129,9943,4982,4440,1793,2642,7575,5830,6273,2970,1380,6218,7215,8879,937,1987,5576,2896,6408,3060,2466,3793,5932,3078,992,9694,2490,1754,7744,5849,5105,8942,1367,2138,2042,7470,1601,3182,7678,4171,9861,7595,6239,2225,9719,5298,8775,6584,8995,9623,4000,3630,1945,5220,4207,2394,2370,839,8051,7428,1421,2520,6230,3681,3864,7006,9510,9746,1262,8043,1032,1096,8350,1304,7254,8716,6741,4904,4083,7197,6558,4113,5194,6409,6132,7171,705,6725,3264,1884,8607,2234,8184,1127,8110,9531,3046,8572,1445,7807,6636,9296,6826,9813,8734,4221,1991,8883,1565,3414,3491,2660,666,387,9022,6346,3781,7424,1505,21,2168,3649,9402,5904,6219,3378,4511,1231,164,1587,8941,8163,575,3009,8576,6655,5539,6329,751,3563,1557,657,9734,490,5146,943,5120,196,8256,8947,7992,3667,4527,5672,6796,5794,4193,1375,6660,9387,2673,2363,8421,7392,2640,5756,8148,4413,8052,5404,578,4959,2239,9656,281,4589,5294,3189,316,6217,4124,5759,9804,2577,2181,1670,6729,9556,592,3806,1698,8321,1834,4428,955,5482,9201,7499,655,2483,3212,3254,2607,1906,6766,2004,7190,4822,1531,7242,6175,6949,3596,7120,3952,2544,8976,3315,7146,9758,2948,6141,1612,2437,6734,5439,811,8672,1791,9176,7510,96,9818,7401,3655,4190,7288,4954,9282,3559,4561,8855,9593,981,118,535,5348,9635,7654,4297,3116,9219,7496,9952,4838,5681,1616,5775,1441,7481,3432,4882,4670,661,3259,8810,1250,587,7616,4396,8703,8548,5075,7708,1898,3398,4168,8800,4482,1157,554,3866,6371,4349,5434,5349,6937,5469,727,7093,9604,1514,8723,8049,5487,7926,4233,2205,4081,9114,4310,5291,2942,172,4107,6529,9375,9071,5151,3141,413,5546,6541,4255,8472,790,2720,4537,5799,1958,8317,2974,409,8357,2125,7809,5405,6714,2703,9374,269,17,1109,8969,960,5113,3325,7449,3374,5682,2321,3204,7665,801,1552,6467,7344,786,9390,7909,4115,2272,479,9967,7511,8953,6550,1110,2818,7247,217,1063,302,2039,5896,2227,3490,7267,9770,8135,7252,9026,3757,499,7100,4033,310,5958,3322,1170,3599,654,6814,6695,597,4601,905,8986,6543,2838,1332,1703,6114,791,9514,4708,9878,9018,9835,5457,3161,3174,1270,9350,3406,2094,8910,4662,3819,2207,3534,3055,7468,5302,3066,4980,9686,6306,4040,1643,6992,5813,8945,5177,7395,5012,8377,4693,3436,8281,5278,8223,6169,7398,9262,8341,4542,103,6563,6531,5821,6618,639,5346,7107,9122,3142,3515,7645,721,2085,3320,1054,3437,5517,4184,7780,3635,7161,4252,4223,8794,2854,5324,6148,500,3442,6611,7129,5894,4367,5934,2170,6960,3752,2521,3469,8274,2895,9024,7641,5323,2286,2099,8822,783,9963,7682,5005,6391,5573,6887,602,4063,8807,2900,2046,2238,3255,4454,3891,4592,5809,2853,2727,4358,6192,6095,1158,3379,1278,1817,8131,2667,7873,5882,3770,533,4418,1605,3974,6763,7740,1760,7090,3342,8523,7783,5187,396,1431,4214,1929,8084,400,489,9234,9775,5428,7592,514,4119,5176,9442,4658,4174,3957,2778,784,412,6551,7233,7086,5902,1108,9198,8742,7484,6461,4721,133,1362,8383,5957,9127,4338,1265,7897,3602,4884,7174,6517,5981,9366,586,5625,4038,7704,4777,5531,3804,9902,3289,47,630,6393,5524,3345,711,121,511,5959,7867,3284,4741,5015,8445,2235,5567,8808,5499,8936,964,7356,3980,3002,3123,7981,69,924,6040,3521,2665,2678,5767,5403,5715,7515,2572,6587,5719,3870,1761,2215,7151,8921,873,8459,6987,5253,1428,9772,8724,126,9693,8067,8165,9489,7418,37,59,2543,7485,6919,8933,6746,9615,3858,2404,6866,8594,109,8772,6457,4369,3340,191,4479,7543,4530,6882,3735,1540,9752,5986,9528,7350,6837,402,2620,4960,6654,9407,8788,9937,7804,768,6519,5041,3191,8180,52,5963,2142,1383,7869,3475,7007,3314,2688,12,820,5225,2216,6545,5182,9504,6247,9913,6601,2431,6481,6243,8981,7203,9443,6748,8241,3176,7798,1154,8860,7811,5699,1309,4965,3775,8762,7123,2093,698,9308,2877,8343,9404,971,6861,8500,3555,7072,5590,7895,3739,2357,2012,1360,2047,3265,5923,6076,6508,314,6016,2061,184,6185,9578,2791,4871,9872,5117,3483,3244,7149,44,718,7230,8554,9380,8511,8865,4196,3601,663,4102,7765,8330,8903,5258,9783,6448,4219,4057,3939,4655,1924,2735,6021,4557,2776,863,2411,9260,9475,3954,204,4014,7620,2281,9354,366,3506,5251,9290,1321,4543,6540,2536,1774,6304,7480,9173,4006,7819,255,3133,7000,6177,9017,4444,9049,7381,250,1394,6525,1757,4556,6389,6607,8345,7208,8270,6891,1077,756,2033,2045,958,8893,7362,1594,3741,5415,5036,6452,3422,6030,5518,3102,6512,6881,18,5490,8483,1090,4162,125,4266,496,105,8217,5038,4800,9620,8260,1244,6828,1310,563,2787,9629,4643,4615,2182,8158,6982,3983,8308,2459,4110,1206,9541,9265,8412,8967,3323,6792,2044,858,3899,8854,5848,4302,7363,9336,1830,3780,1104,6232,1750,6638,9763,7223,4314,1857,9626,8034,3623,9803,9365,4618,9930,5941,2479,433,6625,5784,7138,4105,14,4243,6109,5209,954,8118,7291,7534,7689,6571,8362,6012,4268,6859,2153,4331,5066,2155,8111,9522,5475,808,2278,3276,8549,3788,4551,9325,1731,2801,6832,5444,2819,8169,8830,7447,1948,8847,2724,794,8747,452,280,8334,7552,2014,4028,4627,3825,2217,612,3082,3194,7506,8998,7519,7435,8632,1040,749,2190,2412,8354,2995,1787,497,2070,9841,4031,5748,3609,192,1614,6572,632,1971,2783,4074,9701,7564,6411,226,1969,5160,8435,8991,4654,5130,9900,6117,3383,6295,236,3062,2920,4478,5215,1320,2024,8529,1574,5534,9415,6825,5818,6799,7907,4486,4798,4573,4385,3710,2183,7535,4734,867,6608,6125,9207,8060,7958,3357,2699,9203,6567,5307,9233,6988,1434,7959,7366,6612,4668,4713,6055,6651,8150,4808,4701,7057,5483,7594,6325,942,6588,875,5498,1842,2307,5964,793,7856,7092,1464,7152,5795,531,3364,1702,1326,5944,6856,4832,6886,9485,1867,8957,6190,7256,6456,7699,8761,8042,9899,5311,9965,1983,5358,3223,9115,8442,7758])
print(qqq)

# =============================================================================
# class Solution(object):
#     def isValid(self, s):
#         """
#         :type s: str
#         :rtype: bool
#         """
#         a = {')':'(', ']':'[', '}':'{'}
#         l = [None]
#         for i in s:
#             if i in a and a[i] == l[-1]: # 左边的入栈,右边的出栈
#                 l.pop()
#             else:
#                 l.append(i)
#         return len(l)==1        # 如果不匹配就会!= 1,所以返回False
# 
# sss =  Solution()
# qqq = sss.isValid(")[]{}")
# print(qqq)
# =============================================================================

# =============================================================================
# class Solution:
#     def generate(self, numRows):
#         """
#         :type numRows: int
#         :rtype: List[List[int]]
#         """
#         res = []
#         for i in range(numRows):
#             res.append([1])
#             for j in range(1,i+1):
#                 if j==i:
#                     res[i].append(1)
#                 else:
#                     res[i].append(res[i-1][j-1]+res[i-1][j])
#         return res
#             
# sss =  Solution()
# qqq = sss.generate(5)
# =============================================================================
# =============================================================================
# # 0000 0010 1001 0100 0001 1110 1001 1100
# # 0b10 1001 0100 0001     1 110 1001 1100
# # 4       3    2    6    1   5    9    6
# n = bin(43261596)
# 
# class Solution:
#     # @param n, an integer
#     # @return an integer
#     def reverseBits(self, n):
#         b = list('{:032b}'.format(n))
#         for i in range(16):
#             b[i],b[31-i] = b[31-i],b[i]
#         r = int(''.join(b),2)
#         return r
#         
# sss =  Solution()
# qqq = sss.reverseBits(43261596)
# =============================================================================
        
# =============================================================================
# class Solution(object):
#     def hammingDistance(self, x, y):
#         """
#         :type x: int
#         :type y: int
#         :rtype: int
#         """
#         n =  x ^ y
#         count = 0
#         while n:
#             n = n & (n-1)
#             count += 1
#         return count
#         
# 
# sss =  Solution()
# qqq = sss.hammingDistance(x = 1, y = 4)
# =============================================================================
        
# =============================================================================
# class Solution(object):
#     def hammingWeight(self, n):
#         """
#         :type n: int
#         :rtype: int
#         """
#         aaa = bin(n)
#         total = 0
#         for i in range(2, len(aaa)):
#             total += int(aaa[i])
#         return total
# =============================================================================
    
# =============================================================================
# class Solution(object):
#     def hammingWeight(self, n):
#         """
#         :type n: int
#         :rtype: int
#         """
#         count = 0
#         while n:
#             n = n & (n - 1)
#             count += 1
#         return count
#             
#         
#         
# sss =  Solution()
# qqq = sss.hammingWeight(9)   
# =============================================================================
